package com.mlamp动态规划问题;

import java.util.Arrays;

public class 最长重复子数组 {

    public static void main(String[] args) {
        最长重复子数组 instance = new 最长重复子数组();
        int[] A = new int[]{1, 2, 3, 2, 1};
        int[] B = new int[]{3, 2, 1, 4, 7};
        int result = instance.findLength(A, B);
        System.out.println("result =" + result);
        result = instance.findLenth(A, B);
        System.out.println("res= " + result);
    }

    public int findLength(int[] A, int[] B) {
        int n = A.length, m = B.length;
        int[][] dp = new int[n + 1][m + 1];
        int ans = 0;
        for (int i = n - 1; i >= 0; i--)
            for (int j = m - 1; j >= 0; j--) {
                dp[i][j] = A[i] == B[j] ? dp[i + 1][j + 1] + 1 : 0;
                ans = Math.max(ans, dp[i][j]);
            }
        return ans;
    }

    public int findLenth(int A[], int B[]) {
        int a_len = A.length, b_len = B.length;
        int[][] dp = new int[a_len + 1][b_len + 1];
        int ans = 0;
        for (int i = a_len - 1; i >= 0; i--)
            for (int j = b_len - 1; j >= 0; j--) {
                dp[i][j] = A[i] == B[j] ? dp[i + 1][j + 1] + 1 : 0;
                ans = Math.max(dp[i][j], ans);
            }
        return ans;
    }
}
